import java.util.Stack;

public class LargestRectangleArea {

    public static void main(String[] args) {
        LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
        int[] nums = {2, 1, 2};
        System.out.println(largestRectangleArea.largestRectangleArea(nums));
    }

    public int largestRectangleArea1(int[] heights) {
        int n = heights.length;
        if (n == 1) return heights[0];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int indexL = i - 1;
            int indexR = i + 1;
            for (int j = i - 1; j >= 0; j--) {
                if (heights[i] > heights[j]) {
                    indexL = j;
                    break;
                }
                if (j == 0) indexL = -1;
            }
            for (int j = i + 1; j < n; j++) {
                if (heights[i] > heights[j]) {
                    indexR = j;
                    break;
                }
                if (j == n - 1) indexR = n;
            }
            ans = Math.max(ans, heights[i] * (indexR - indexL - 1));
        }
        return ans;
    }

    public int largestRectangleArea(int[] heights) {
        if (heights.length == 1) return heights[0];
        int n = heights.length;
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        stack.push(0);
        for (int i = 1; i < n; i++) {
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                Integer index = stack.pop();
                ans = Math.max(ans, heights[index] * (i - (stack.isEmpty() ? -1 : stack.peek()) - 1));
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer index = stack.pop();
            ans = Math.max(ans, heights[index] * (n - (stack.isEmpty() ? -1 : stack.peek()) - 1));
        }
        return ans;
    }
}
